package com.sfx.算法专题.滑动窗口.变化窗口;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-09
 * Time: 10:49
 */
public class Code_6_minWindow {
    static class Solution1 {
        public String minWindow(String ss, String tt) {
            int left = 0;
            int right = 0;
            char[] s = ss.toCharArray();
            char[] t = tt.toCharArray();
            int[] hash1 = new int[128];
            int[] hash2 = new int[128];
            for (char c : t) {
                hash1[c]++;
            }
            int cnt = 0;
            int res = Integer.MAX_VALUE;
            int n = ss.length();
            int m = tt.length();
            int index1 = 0;
            int index2 = 0;
            while (left < n) {
                while (cnt < m && right < n) {
                    //进窗口前更新
                    if (hash2[s[right]] < hash1[s[right]]) {
                        cnt++;
                    }
                    //进窗口
                    hash2[s[right]]++;
                    right++;
                }
                //更新结果
                if (cnt == m && res > (right - left)) {
                    res = right - left;
                    index1 = left;
                    index2 = right;
                }
                //出窗口
                hash2[s[left]]--;
                //出窗口后更新cnt
                if (hash2[s[left]] < hash1[s[left]]) {
                    cnt--;
                }
                left++;
            }
            return ss.substring(index1, index2);
        }
    }

    static class Solution2 {
        public String minWindow(String ss, String tt) {
            if (ss.length() < tt.length()) return "";
            char[] s = ss.toCharArray(), t = tt.toCharArray();
            int[] hash1 = new int[128], hash2 = new int[128];
            for (char c : t) hash1[c]++;
            int n = ss.length(), kinds = tt.length(), left = 0, right = 0, begin = -1, cnt = 0, res = Integer.MAX_VALUE;
            while (right < n) {
                //进窗口前更新
                if (hash2[s[right]] < hash1[s[right]]) cnt++;
                //进窗口
                hash2[s[right]]++;
                while (cnt == kinds) {
                    //更新结果
                    if (right - left + 1 < res) {
                        res = right - left + 1;
                        begin = left;
                    }
                    //出窗口
                    hash2[s[left]]--;
                    //出窗口后更新cnt
                    if (hash2[s[left]] < hash1[s[left]]) cnt--;
                    left++;
                }
                right++;
            }
            if (begin == -1) return "";
            return ss.substring(begin, begin + res);
        }
    }
}